\subsubsection{Traitement des données redondantes}
\paragraph{Les structures identiques}
~\\

Pour identifier les données identiques dans RNALfold, il faut d'abord comprendre comment se présentent les pre-miARN\footnote{Tige-boucle candidat de microARN}. Ces derniers commencent forcément par un appariement, la représentation dot-bracket de leur structure secondaire commence alors par une parenthèse ouvrante et se termine par une parenthèse fermante, avec à l'intérieur de ces parenthèses une structure secondaire quelconque:
\\
\begin{center}
($\underbrace{\ldots\ldots\ldots}_{une\ structure\ quelconque...}$)
\end{center}
~\\
\\
Voici une série de structures secondaires avec les doublons mises en évidence (Pour alléger la lecture j'ai omis l'énergie, l'entier correspond à la position de départ) :


  \begin{center}
  ( . \textcolor{green}{( \ )} . ) \textcolor{blue}{( . . (  \ ) . )} \ \ 1
  \\(\ )\ \textcolor{blue}{( . . (  \ ) . )}\ \textcolor{red} {(\ .\ )}\ \ 5
  \\ . \textcolor{green}{( \ )} .   \ \ 2
  \\$\underbrace{(\ .\  )}_{\alpha }$\ .\ .\ \textcolor{red} {(\ .\ )}\ \ 9
   
  \end{center}
 


Il faut bien comprendre qu' $\alpha$ n'est pas identique aux sous-structures rouges à cause de sa position dans la séquence.
\\
\\

Les structures à considérer pour la recherche de pre-miARN sont alors:
\begin{center}
  ( . \textcolor{green}{( \ )} . )\ \ 1
  \\ \textcolor{blue}{( . . (  \ ) . )}\ \ 7
  \\(\ )\ \ 5
  \\ \textcolor{red} {(\ .\ )}\ \ 14
  \\(\ .\ )\ \ 9
\end{center}

\paragraph{Utilisation d'une matrice}
~\\
\\

Soit $n$, la longueur de la séquence d'ARN à traiter.

Dans un premier temps, j'ai utilisé une matrice carrée de taille $n$, qui sera utilisée pour marquer les appariements rencontrés. 

L'idée consiste à parcourir les structures et à chaque appariement trouvé on pose un marquage, plus précisément en indiquant le numéro\footnote{indice dans le tableau qui contient toutes les structures prédites} de la séquence. Ainsi pour une structure qui se trouve à la position $k$ dans le tableau qui regroupe toutes les structures, si on rencontre un appariement $i,j$ on met la valeur $k$ à la positon $i,j$ dans la matrice. 
~\\
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.2]{../imports/i_j.png}
\caption{\label{insertion} Insertion matrice}
\end{center}
\end{figure}
\\

De ce fait, si pour une autre structure $k'$, on rencontre le même appariement $i,j$ alors la valeur de la matrice à la position $i,j$ reste inchangée. On est donc sûr de traiter l'appariement $i,j$ et donc la tige-boucle qui commence à la position $i$ qu'une seule fois. 

Par exemple si on considère l'illustration des redondances utilisée et en considérant que les structures soient numérotées dans l'ordre croissant , avec une taille de séquence égale à 16 on a:
\\
\\
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.7]{../imports/matrice_n_n.png}
\caption{\label{matrice_n_n} Matrice pour traiter les redondances}
\end{center}
\end{figure}
\\
\\
\newpage
\paragraph{Réduction de la matrice}
~\\

Il est inutile de considérer les appariements $i,j$ avec $j < i$ qui correspondent aux appariements situés sur le deuxième brin de la tige. En effet par symétrie si le nucléotide i est apparié avec le nucléotide $j$, $j$ l'est également avec $i$. On peut alors réduire la matrice de moitié.

En plus de cela, les tiges boucles susceptibles de donner un microARN ont une taille minimale $\beta$\footnote{paramètre défini par les biologistes} et maximale $\alpha $\footnote{idem}. Ce qui permet encore de réduire la matrice.

Pour résumer on a donc:
\begin{center}
\
  \textcolor{green}{$j-i>\beta$}\\
  \textcolor{red}{$j-i<\alpha$}\\
  \textcolor{blue}{$j<i$}
\end{center}

Si on considère que $\alpha=10$ et $\beta=3$, cela nous donne:
\\
\\
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.7]{../imports/matrice_finale.png}
\caption{\label{matrice_finale} Découpage}
\end{center}
\end{figure}
\\
\newpage
Il n'est donc nécessaire de ne garder qu'une sous-partie de la matrice initiale, ce qui permet d'économiser de l'espace mémoire.
\\
\\
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.7]{../imports/matrice_reduit.png}
\caption{\label{matrice_reduit} Matrice finale}
\end{center}
\end{figure}
\\

$i$ reste la position dans la séquence mais $j$ ne correspond plus à la position réelle, en réalité si à la case $i$, $j$ on a une structure $k$ alors il y a un appariement entre les nucléotides $i$ et $i+j+\beta$. 
La lecture du tableau nous donne les structures à considérer. Dans l'exemple on doit prendre en compte deux structures qui appartiennent  à la même structure, prédite par RNALfold, d'indice 1.
\\
\begin{itemize}
 \item Pour la case 1,2: Une structure entre les positions 1 et $1+2+\beta=6$
  \item Pour la case 7,3: Une structure entre les positions 7 et $7+3+\beta=13$
\end{itemize}
~\\

Soit les structures:
\begin{center}
  ( . \textcolor{green}{( \ )} . )\ \ 1
  \\ \textcolor{blue}{( . . (  \ ) . )}\ \ 7
\end{center}
~\\
\input{inclusion.tex}
\input{last_match.tex}
